/**
 * 时间复杂度：最坏情况：5 4 3 2 1 逆序情况下相当于每次都要挪动i-1次  O(N^2)
 *          最好情况下：1 2 3 4 5 有序情况下不用挪动 O(N)
 *          空间复杂度O(1)
 *          稳定性：稳定
 *          一个本身就稳定的排序，可以实现为不稳定
 *          但是一个本身就不稳定的排序，不可能实现为稳定的排序
 *          当数据越有序的时候，直接插入排序效率越高
 */
public class InsertSort {
    public static void insertSort(int[] array) {
        for(int i = 1; i < array.length;i++) {
            int tmp = array[i];
            int j = i - 1;
            for(;j >= 0; j--) {
                //此处为稳定，如果加个等于就变为不稳定了
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
}
